/**
 * 0094
 *  
 * @Author : roryrywang
 * @DateTime : 2024/8/14 21:59
 */

#include <iostream>
#include <vector>
#include "stack"

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

// 递归实现中序遍历
//class Solution {
//private:
//    vector<int> res;
//
//    void inorder(TreeNode *root) {
//        if (root == nullptr)return;
//        inorder(root->left);
//        res.push_back(root->val);
//        inorder(root->right);
//    }
//
//public:
//    vector<int> inorderTraversal(TreeNode *root) {
//        inorder(root);
//        return res;
//    }
//};

// 非递归实现中序遍历
class Solution {
private:
    vector<int> res;
    stack<TreeNode *> s;
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> res;
        stack<TreeNode *> s;
        TreeNode *cur = root;
        while (cur != nullptr || !s.empty()) {
            if (cur == nullptr) {
                cur = s.top();
                s.pop();
                res.push_back(cur->val);
                cur = cur->right;
            } else {
                if (cur->left != nullptr) {
                    s.push(cur);
                    cur = cur->left;
                } else {
                    res.push_back(cur->val);
                    cur = cur->right;
                }
            }
        }
        return res;
    }
};

int main() {
    Solution sl;
    TreeNode *c = new TreeNode(3);
    TreeNode *b = new TreeNode(2, c, nullptr);
//    TreeNode *a = new TreeNode(1, nullptr, b);
    TreeNode *a = new TreeNode(1);
    vector<int> res = sl.inorderTraversal(a);
    for (int i = 0; i < res.size(); ++i) {
        cout << res[i] << " ";
    }
    cout << endl;
    return 0;
}